РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 6 7 8 9
Атрибут

Всего: 115 1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

Тип 0 № 75 Добавить в вариант

В футбольном турнире участвовало 10 команд, каждая из которых с каждой из остальных сыграла по одному матчу. По окончании турнира выяснилось, что для любой тройки команд найдутся две команды из этой тройки, набравших равное число очков в играх с командами из этой тройки. Доказать, что все команды можно разбить не более, чем на три подгруппы таких, что любые две команды из одной подгруппы сыграли между собой вничью. За выигрыш в футболе команда получает 3 очка, за ничью  — 1 очко и за проигрыш  — 0 очков.

Решение.

1.  Сначала выясним, как могли сыграть три команды между собой с соблюдением условий задачи. Если внутри тройки не было ничьих, единственным подходящим вариантом будет (Т1), когда каждая проиграла и выиграла по одному матчу, у всех по 3 очка. Если ничья была ровно одна, то сделавшие её команды либо обе выиграли у третьей (Т2: 4,4 и 0 очков), либо обе проиграли третьей (Т3: 1,1 и 6 очков). Случай ровно с двумя ничьими невозможен. Подходит и вариант с тремя ничьими (Т4): все набирают по 2 очка.

2.  Из пункта 1 следует, что: а) Если две А и Б команды сыграли между собой вничью, то результаты матчей любой другой команды с А и с Б одинаковы. б) Если команда сыграла с командами А и Б с одинаковым результатом, то А и Б сыграли между собой вничью.

3.  Докажем, что в турнире была хотя бы одна ничья. В противном случае, всего имеем 45 побед во всех матчах, значит, найдётся команда А, выигравшая не меньше 5 матчей. Рассмотрим команды Б и В, проигравшие А, очевидно, что тройка А, Б, В не удовлетворяет условию задачи.

4.  Обозначим какие-нибудь команды, сыгравшие между собой вничью, за А и Б. В первую подгруппу включим все команды, сыгравшие с А и Б вничью, во вторую все команды, выигравшие у А и Б, в третью  — все команды, проигравшие А и Б. Из пункта 2.б) следует, что в пределах каждой подгруппы все команды сыграли между собой вничью.

Критерии оценивания выполнения задания	Баллы
Верный ответ.	7
Пункт 1.	2
Пункт 2.	1
Пункт 3.	1
Пункт 4.	3
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

Решение · Критерии · Помощь

Тип 0 № 283 Добавить в вариант

В турнире каждая из шести команд сыграла с каждой ровно по одному разу. В итоге команды набрали 12, 10, 9, 8, 7 и 6 очков соответственно. а) Сколько очков начислялось за победу в матче, если за ничью начислялось 1 очко, а за поражение  — 0 очков? Ответом, естественно, должно быть натуральное число. б) Найдите количество выигрышей, ничьих и проигрышей у каждой команды и докажите единственность этих чисел. в) Приведите пример соответствующего турнира.

Решение.

а)  Пусть за победу в матче команде начислялось n очков, всего в турнире было сыграно 15 матчей, из которых x окончились победой одной из команд, а остальные 15 − x  — вничью. В ничейных матчах участники в сумме набирают 2 очка, а в остальных  — n очков, поэтому всего в турнире всеми командами было набрано $nx плюс 2 левая круглая скобка 15 минус x правая круглая скобка = левая круглая скобка n минус 2 правая круглая скобка x плюс 30=12 плюс 10 плюс 9 плюс 8 плюс 7 плюс 6=52$ очка, откуда $левая круглая скобка n минус 2 правая круглая скобка x=22.$ Всего игр было 15, поэтому x может равняться 1, 2 или 11. В первых двух случаях n равно 24 или 13, что превосходит максимальное количество очков, набранных командами, чего быть не может, так как победа в матче становится невозможной в принципе, значит, все матчи окончатся вничью, что противоречит предположению о x. В оставшемся случае x равен 11, тогда n равно 4  — количество очков, начисляемое за победу.

б)  Найдём количество выигрышей, ничьих и проигрышей у каждой команды. Всего было четыре ничьих и 11 матчей, окончившихся победой одной из команд. Каждая команда провела по пять игр, поэтому 6 и более очков нельзя было набрать только за счёт ничьих, следовательно, шестая и пятая команды по разу выиграли и сделали по две и три ничьих соответственно. Если бы четвёртая команда выиграла не более одного раза, у неё было бы не меньше четырёх ничьих, всего вместе с пятой и шестой было бы уже не меньше $левая круглая скобка 2 плюс 3 плюс 4 правая круглая скобка :2=4,5$ ничьих, что больше общих 4. Следовательно, четвёртая команда дважды выиграла и трижды проиграла. В силу тех же соображений у третьей команды две победы и одна ничья, у второй  — две победы и две ничьих. У всех команд, кроме первой, получаем не меньше $левая круглая скобка 2 плюс 3 плюс 1 плюс 2 правая круглая скобка :2=4$ ничьих, что равно их общему числу. Следовательно, у первой команды было три победы и два поражения.

в)  Приведём пример соответствующего турнира. Пятая команда трижды сыграла вничью, а упервой и четвёртой  — ничьих не было. Значит, пятая команды сыграла вничью с шестой, третьей и второй. Кроме этих ничьих, остаётся по одной у шестой и второй, поэтому они сыграли вничью между собой. Всё, ничьи закончились, и они восстанавливаются однозначно. А вот результативные матчи однозначно восстановить нельзя. Один из примеров, удовлетворяющих условию, такой: первая команда выиграла у четвёртой, пятой и шестой, вторая  — у первой и третьей, третья  — у первой и шестой, четвёртая  — у второй и третьей, пятая  — у четвёртой, шестая  — у четвёртой.

Ответ: а) 4 очка. б) У первой команды было три победы, у второй  — две победы и две ничьих, у третьей  — две победы и одна ничья, у четвёртой  — две победы, у пятой  — одна победа и три ничьи, у шестой  — одна победа и две ничьи. Остальные матчи команды проиграли. в) Один из примеров, удовлетворяющих условию, такой: первая команда выиграла у четвёртой, пятой и шестой, вторая  — у первой и третьей, третья  — у первой и шестой, четвёртая  — у второй и третьей, пятая  — у четвёртой, шестая  — у четвёртой. При этом пятая команды сыграла вничью с шестой, третьей и второй, а также вничью сыграли шестая и вторая команды.

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Правильный и обоснованный ответ в пункте а).	3
Найдено с обоснованием количество побед и ничьих у каждой команды.	2
Приведён любой верный пример турнира в пункте в).	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

Решение · Критерии · Помощь

Тип 0 № 292 Добавить в вариант

В футбольном турнире участвовали 17 команд, каждая из которых сыграла с каждой изостальных по одному разу. Могло ли у каждой команды число одержанных ею победравняться числу матчей, сыгранных ею вничью?

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Показано, что общее число всех одержанных побед будет равнообщему числу всех поражений.	2
Показано, что оба этих количества равны общему числу всех ничьих.	3
Проведено суммирование количеств всех побед, ничьих ипоражений всех команд и показано, что оно не делится на 3.	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

Решение · Критерии · Помощь

Тип 0 № 449 Добавить в вариант

По регламенту шахматного турнира каждый участник должен сыграть с каждым один раз. После того как было сыграно ровно 99 партий, оказалось, что множество участников турнира можно разбить на две неравные по численности группы так, что все соперники, относящиеся к одной и той же группе, уже сыграли партии между собой. При этом были сыграны, но не более четырех, партии между соперниками, которые относятся к разным группам. Каково наибольшее возможное число участников этого шахматного турнира?

Критерии оценивания выполнения задания	Оценка	Баллы
Полное решение.	+	14
Ответ верный. Приведены обоснованные верные оценки для наибольшего числа участников турнира. Отсутствует строгое обоснование приведенных оценок или ответа.	±	11
Ответ верный. Приведены обоснованные верные оценки для наибольшего числа участников турнира. Отсутствует строгое обоснование приведенных оценок и ответа. ИЛИ Ответ верный. Приведены верные, но не обоснованные оценки для наибольшего числа участников турнира. Приведено строгое обоснование ответа по указанным оценкам.	+/2	7
Ответ неверный или отсутствует. В решении приведены обоснованные оценки для оценки для наибольшего числа участников турнира или составлены верные соотношения, из которых они получаются.	∓	3
Решение не соответствует ни одному критерию, описанному выше.	−/0	0
Максимальный балл	14

Решение · Критерии · Помощь

Тип 0 № 2052 Добавить в вариант

В шахматном кружке занимаются мальчики и девочки. Их разбили на группы по 6 человек, при чем в каждой группе есть и девочки и мальчики. В каждой группе прошел круговой турнир, каждый сыграл по одной партии с каждым из остальных членов той же группы, других игр не было. Может ли при этом число партий между мальчиками быть на 23 больше числа партий между девочками?

Критерии проверки:

Вид погрешности или ошибки	Отметка в работе	Баллы
Каждая задача оценивается по 10-балльной шкале и снабжается отметкой в работе 0, −, ∓, ±, + в соответствии с критериями.
Решение задачи верное, выбран рациональный путь решения	+	10
Решение верное, но путь не рационален или имеются один  — три недочета или негрубая ошибка	+	9
Решение верное, но путь не рационален и имеются один  — три недочета или негрубая ошибка	±	7−8
Ход решения верный, но есть несколько негрубых ошибок или решение не завершено	∓	5−6
Допущены грубые ошибки, но ответ получен (неверный)	∓	3−4
Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато  — без ошибок	−	2
Решение начато, но продвижение ничего не дает для результата	−	1
Задача не решилась	0	0
Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки:    I.  Логические, приводящие к неверному заключению.   II.  Арифметические ошибки, искажающие смысл ответа. III.  Неверный чертеж в геометрических задачах. IV.  Принципиальные ошибки в применении элементарных формул и теорем.

Решение · Критерии · Помощь

Тип 0 № 2464 Добавить в вариант

На однокруговой турнир по настольному теннису подало заявку 16 человек. Когда было сыграно n матчей, оказалось, что среди любых трех теннисистов найдутся двое, уже сыгравших между собой. При каком наименьшем n такое возможно?

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

1 балл  — выставляется, если участник приступил к решению задачи, указал верное направление решения задачи и получил правильные промежуточные результаты, но при этом не продвинулся настолько, чтобы можно было судить о том, каким образом он собирался получить окончательный ответ (то есть весь ход решения не представлен);

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

4 балла  — выставляется, если участник решил задачу в целом правильно и получил верный ответ; при этом в решении допускаются незначительные неточности.

Факторы, влияющие на оценку.

1.  Одна из основных целей Олимпиады  — выявление у обучающихся творческих способностей. Поэтому в случае представления участником интересного оригинального подхода к решению задачи, оценка за решение может быть увеличена на 1 балл.

2.  Правильный ответ к задаче, приведенный без достаточных обоснований, либо при наличии ошибок в решении, либо при отсутствии решения, не ведёт к увеличению оценки, которая выставляется участнику за данную задачу.

3.  Если участник не довел задачу до ответа, то итоговая оценка за данную задачу не может превышать 1 балл.

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

5.  Если задача решена при дополнительном предположении, которое отсутствует в условии, то за задачу выставляется

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Решение · Критерии · Помощь

Тип 0 № 2470 Добавить в вариант

В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков A, B, C, D, что A выиграл у B, B  — у C, C  — у D, D  — у A. Каково наибольшее количество троек участников, одержавших во встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

Решение.

Назовем циклом такую тройку участников, что во встречах между собой каждый из них одержал по одной победе. Докажем вначале, что ни один теннисист не может входить более чем в один цикл. Договоримся символом $A arrow B$ отмечать факт победы A над B. Пусть нашелся участник C, фигурирующий в двух разных циклах. Эти циклы могут быть двух типов:

1)  (A, B, C) и (C, D, E). Тогда $A arrow D,$ так как иначе

$A arrow B arrow C arrow D arrow A,$

что невозможно. Но в этом случае $A arrow D arrow E arrow C arrow A,$ чего так же быть не может;

2)  (A, B, C) и (B, C, D). Тогда вновь $A arrow D.$ Но в этом случае

$A arrow D arrow B arrow C arrow A,$

что также невозможно. Таким образом, в два цикла теннисист C входить не может.

По доказанному циклы не пересекаются, поэтому их количество не превосходит $левая квадратная скобка дробь: числитель: 35, знаменатель: 3 конец дроби правая квадратная скобка =11.$ Приведем пример турнира с 11 циклами. Разобьем 33 участника на группы по 3 человека и занумеруем эти группы числами от 1 до 11. Пусть каждая группа образует цикл, а во встрече теннисистов, входящих в разные группы, побеждает спортсмен из группы с большим номером. Наконец, оставшиеся два участника побеждают всех остальных. Такой турнир удовлетворяет условию задачи и имеет ровно 11 циклов.

Ответ: 11.

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 0 № 2476 Добавить в вариант

В однокруговом турнире по настольному теннису приняло участие 25 человек. Кадый теннисист одержал по 12 побед. Сколько по итогам турнира оказалось троек участников, одервших во встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

Решение.

Назовем циклом такую тройку участников, что во встречах между собой каждый из них одержал по одной победе. Обозначим через x общее количество циклов, а через y  — количество всех троек, не образующих цикла. Тогда $x плюс y$   — общее число различных троек участников, откуда $x плюс y=C_25 в кубе =2300.$

Рассмотрим теперь упорядоченные тройки участников (A, B, C), в которых A победил B, а B выиграл у C. Если теннисисты A, B, C не образуют цикла, их можно упорядочить однозначно, а если образуют  — тремя способами (подходят также циклические перестановки тройки). Значит, общее число упорядоченных троек равно $3 x плюс y.$ С другой стороны, для каждого теннисиста B его партнеров по тройке A и C можно выбрать независимо двенадцатью способами, поскольку B потерпел 12 поражений и одержал 12 побед. Поэтому всего есть $12 умножить на 12 умножить на 25=3600$ упорядоченных троек, откуда $3 x плюс y=3600.$ Таким образом,

$x= дробь: числитель: 1, знаменатель: 2 конец дроби левая круглая скобка 3 x плюс y минус левая круглая скобка x плюс y правая круглая скобка правая круглая скобка = дробь: числитель: 1, знаменатель: 2 конец дроби левая круглая скобка 3600 минус 2300 правая круглая скобка =650 .$

Ответ: 650.

Приведем другое решение. Пусть в турнире участвовало $2 k плюс 1$ теннисистов, и каждый одержал по k побед. Назовем циклом такую тройку участников, что во встречах между собой каждый из них одержал по одной победе. Обозначим через S_k общее количество циклов в турнире с $2 k плюс 1$ участниками. Ясно, что $S_1=1.$ Добавим в турнир с $2 k минус 1$ участниками двух новых теннисистов A и B и посмотрим, на сколько увеличится число циклов. Пусть A выиграл у B. Тогда остальные $2 k минус 1$ участников разобьются на группы из $k минус 1$ и k человек: первая группа проиграла A и выиграла у B, вторая наоборот.

Новые циклы могут быть двух типов:

1)  (A, C, D) или (B, C, D), где C, D отличны от A и B. Если C и D входят в одну группу, то таких циклов быть не может, поскольку и A и и B либо выиграли у C и D, либо проиграли им. Пусть C взят из первой группы, а D  — из второй. Если C выиграл у D, то (A, C, D) образует цикл, а (B, C, D)  — нет. Если же D выиграл у C, то (B, C, D) образует цикл, а (A, C, D)  — нет. Таким образом, пара (C, D) дает ровно один новый цикл, а общее число циклов первого типа равно $левая круглая скобка k минус 1 правая круглая скобка k;$

2)  (A, B, C), где C отличен от A и B. Такая тройка будет циклом тогда и только тогда, когда C берется из второй группы. Значит, мы получаем еще k новых циклов.

Из 1) и 2) вытекает, что

$S_k минус S_k минус 1= левая круглая скобка k минус 1 правая круглая скобка k плюс k=k в квадрате ,$

откуда для любого натурального n

$S_n=S_1 плюс левая круглая скобка S_2 минус S_1 правая круглая скобка плюс \ldots плюс левая круглая скобка S_k минус S_k минус 1 правая круглая скобка =1 в квадрате плюс 2 в квадрате плюс \ldots плюс n в квадрате = дробь: числитель: 1, знаменатель: 6 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка левая круглая скобка 2 n плюс 1 правая круглая скобка .$

Осталось подставить $n=12.$

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 0 № 2482 Добавить в вариант

В однокруговом турнире по настольному теннису участвовало n теннисистов с различными рейтингами (n > 4). Во всех партиях, кроме двух, победил участник с более высоким рейтингом, но теннисист с самым маленьким рейтингом выиграл у теннисиста с самым большим рейтингом, теннисист с предпоследним рейтингом выиграл у теннисист со вторым рейтингом. Сколькими способами можно расставить спортсменов в ряд так, что каждый (кроме самого правого) выиграл у своего соседа справа?

Решение.

Пусть для простоты рейтинги теннисистов равны $1, 2, \ldots, n.$ Одна расстановка очевидна  — по убыванию рейтинга. В других расстановках убывание нарушается. Это может происходить только из-за присутствия пар соседей $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка$ (какой-то одной или обеих). Рассмотрим три случая.

1)  Bстречается только пара $левая круглая скобка 1, n правая круглая скобка .$ До и после этой пары может быть любое количество теннисистов, но их порядок фиксирован. Припишем спортсмену индекс 0, если он стоит слева от пары, и 1, если справа. Для каждого из оставшихся $n минус 2$ теннисистов допустимы оба индекса, поэтому всего будет $2 в степени левая круглая скобка n минус 2 правая круглая скобка$ расстановок.

2)  Bстречается только пара $левая круглая скобка 2, n минус 1 правая круглая скобка .$ Поскольку пары $левая круглая скобка n минус 1, n правая круглая скобка$ и (1, 2) недопустимы, теннисист с рейтингом n должен стоять первым в ряду, а теннисист с рейтингом 1  — последним. Остальные $n минус 4$ спортсмена могут стоять как до пары $левая круглая скобка 2, n минус 1 правая круглая скобка ,$ так и после нее, но в фиксированном порядке. Таких расстановок всего $2 в степени левая круглая скобка n минус 4 правая круглая скобка .$

3)  Встречаются пары $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка .$ Любой из остальных $n минус 4$ теннисистов может располагаться до первой пары, между парами и после второй пары. Таких расстановок всего $3 в степени левая круглая скобка n минус 4 правая круглая скобка .$ Поскольку пары $левая круглая скобка 1, n правая круглая скобка$ и $левая круглая скобка 2, n минус 1 правая круглая скобка$ могут идти в любом порядке, мы получаем $2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка$ вариантов.

Таким образом, всего возможно

$1 плюс 2 в степени левая круглая скобка n минус 2 правая круглая скобка плюс 2 в степени левая круглая скобка n минус 4 правая круглая скобка плюс 2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка$

расстановок.

Ответ: $1 плюс 2 в степени левая круглая скобка n минус 2 правая круглая скобка плюс 2 в степени левая круглая скобка n минус 4 правая круглая скобка плюс 2 умножить на 3 в степени левая круглая скобка n минус 4 правая круглая скобка .$

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 0 № 2488 Добавить в вариант

В однокруговом турнире по настольному теннису участвовало 100 спортсменов, причем ни один из них не выиграл все матчи. Будем говорить, что игрок A круче игрока B, если A выиграл у B или найдется такой игрок C, что A выиграл у C, С выиграл у B. Каково наименьшее количество теннисистов, оказавшихся по итогам турнира круче всех остальных? Ничьих в теннисе не бывает.

Решение.

Докажем вначале лемму: в произвольном турнире теннисист X, одержавший наибольшее число побед, круче всех. Действительно, пусть Y  — другой участник турнира. Если теннисист X выиграл у Y, то он круче Y. В противном случае Y должен был проиграть кому-то из соперников, у которых X выиграл, иначе Y одержал бы больше побед, чем X. Мы снова получаем, что X круче Y, и лемма доказана.

Рассмотрим теперь турнир, удовлетворяющий у словию задачи. Пусть теннисист A одержал в нем наибольшее число побед. В Силу леммы A круче всех. Обозначим число побед A через k и заметим, что $k меньше 99,$ поскольку A выиграл не все матчи. Предположим, что A победил теннисистов $B_1, \ldots, B_k$ и проиграл cоперникам $C_1, \ldots, C_9 минус k.$ Если учитывать только результаты игр между $C_1, \ldots, C_99 минус k,$ то в этом мини-турнире по лемме найдется участник C*, который круче всех. Кроме A проиграли. Таким образом, C* круче остальных участников всего турнира.

Заметим, что по условию C* должен проиграть кому-то из соперников. Пусть $D_1, \ldots, D_m$   — все участники, выигравшие у C*. По лемме в мини-турнире $D_1, \ldots, D_m$ найдется теннисист D*, который круче всех. Кроме того, D* круче любого участника E не из этого мини-турнир а, поскольку D* выиграл у C*, а C*  — у E. Значит, D* круче остальных участников всего турнира.

Таким образом, всегда существуют по крайней мере три теннисиста (A, C* и D*), которые круче всех. Приведем пример турнира, в котором таких участников ровно 3. Пусть трое теннисистов одержали по одной победе в личных встречах и выиграли у всех остальных. Тогда каждый из этой тройки круче всех, но никто из остальных участников их не круче.

Ответ: 3.

Критерии проверки:

Общая схема:

Факторы, влияющие на оценку.

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

Решение · Критерии · Помощь

Тип 0 № 4206 Добавить в вариант

Четырнадцать теннисистов сыграли в однокруговом турнире (каждый игрок сыграл с каждым одну партию). Докажите, что найдутся такие три игрока, что каждый из остальных 11 игроков проиграл хотя бы одному из этой тройки. (Ничьих в теннисе не бывает).

Решение · Помощь

Тип 21 № 4385 Добавить в вариант

В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу дается 3 очка, за поражение 0 очков, а в случае ничьей играется дополнительное время, победитель которого получает 2 очка, а проигравший  — 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее N матчей закончились дополнительным временем. Найдите наибольшее возможное значение N.

Решение.

Рассмотрим полный ориентированный граф, вершинами которого будут команды  — участницы турнира, в котором ребро между двумя вершинами будет вести от победителя в матче между ними к проигравшему. Покрасим ребро в красный цвет, если встреча закончилась в дополнительное время, и в синий в противном случае.

Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем граф G, в котором количество красных ребер минимально.

Лемма. B красном подграфе графа G нет следующих подграфов:

1)  неориентированных циклов;

2)  ориентированных путей длины 2;

3)  вершин степени 3 и более;

4)  неориентированных путей длины 4.

Доказательство.

Покажем, как можно уменьшить количество красных ребер, если есть описанные выше подграфы.

1.  Предположим, что в G есть неориентированный красный цикл. Тогда зададим на цикле направление обхода, совпадающее с направлением одного из ребер, и сделаем следующую операцию: ребра цикла, которые были ориентированы по направлению обхода, перекрасим в синий, а ориентированные против направления цикла переориентируем по направлению. После такого преобразования распределение очков не поменяется, так как для каждой команды количество очков во встрече с одним из соседей уменьшится на 1, а во встрече с другим увеличится на 1. Количество красных ребер уменьшилось.

2.  Предположим, что в G есть красный ориентированный путь длины 2. Тогда можно считать, что ребро между началом пути и концом  — синее. Если ребро было направлено от начала к концу, то поменяем цвет всех трех ребер, а если из конца в начало, то поменяем цвет и ориентацию всех трех ребер. Заметим, что такое преобразование не меняет количество очков, набранных командой, но уменьшает количество красных ребер.

3.  Предположим, что в G есть вершина A красной степени 3 или более. Тогда выберем трех ее соседей B, C, D. При этом можно считать, что все три красных ребра исходят из вершины A (случай, когда направления различны, невозможен из-за отсутствия пути длины 2, а случай трех входящих аналогичен), а ребра между вершинами B, C, D синие.

Не ограничивая общности, можно считать, что ребра ведут из B в C и из C в D. Получается два случая: в первом ребро ведет из B в D, а во втором из D в B.

Тогда сотрем все ребра между A, B, C, D и нарисуем заново следующим образом:

В обоих случаях рисуем синие ребра из B в A, из A в C, из A в D. В первом случае проведем красные из B в D и из B в C и синее из C в D. Во втором случае проводим красные из D в B и из D в C и синее из C в B.

Итого распределение очков не поменялось, а количество красных ребер уменьшилось.

4.  Предположим, что есть неориентированный красный путь длины 4: A, B, C, D, E. Тогда можно считать, что красные ребра ориентированы следующим образом: $\overrightarrowA B, \overrightarrowC B,$ $\overrightarrowC D,$ $\overrightarrowE D,$ а оставшиеся ребра синие.

Если A обыграла D, то можно изменить ребра AB, BC, CD, AD следующим образом: ребра $\overrightarrowA B,$ $\overrightarrowC D$ сделаем синими, а ребра $\overrightarrowA D,$ $\overrightarrowB C$   — красными. Распределение очков не поменялось, а количество красных ребер уменьшилось, поэтому далее можно считать, что D выиграла у A, а B выиграла у E.

Если B обыграла D, то изменим ребра AB, AD, BC, BD, CD следующим образом: ребра $\overrightarrowC D,$ $\overrightarrowD B,$ $\overrightarrowB A$ сделаем синими, a $\overrightarrowA D,$ $\overrightarrowB C$   — красными.

Если D обыграла B, то изменим ребра BC, BD, BE, CD, DE: ребра $\overrightarrowC B,$ $\overrightarrowB D,$ $\overrightarrowD E$ сделаем синими, а $\overrightarrowE B,$ $\overrightarrowD C$   — красными.

Распределение очков не поменялось, количество красных ребер уменьшилось.

Таким образом, граф на красных ребрах без ориентации является лесом, в котором каждое дерево является цепочкой не более чем из 4 вершин. Тогда количество красных ребер равно $2016 минус T,$ где T  — количество деревьев в графе на красных ребрах. Так как в каждом дереве не более 4 вершин, $T больше или равно 504,$ то есть $N меньше или равно 1512.$

Рассмотрим турнир из 4 команд A, B, C, D. Пусть в нем peбра $\overrightarrowA B,$ $\overrightarrowA D,$ $\overrightarrowC D$   — красные, а ребра $\overrightarrowA C,$ $\overrightarrowB C,$ $\overrightarrowB D$   — синие. Тогда команды A, B набрали по 7 очков, а команды C, D  — по $2 .$

Заметим, что при таком распределении очков должно быть сыграно не менее 3 овертаймов, так как в дополнительное время должны закончится матчи между A и B и между C и D, так как A и B не могли проиграть в основное время, а C и D не могли победить в основное время. Если все оставшиеся матчи завершились в основное время, то суммарное количество очков у A и B будет кратно 3  —противоречие.

Разобьем 2016 команд на четверки (A₁, B₁, C₁, D₁), ..., (A₅₀₄, B₅₀₄, C₅₀₄, D₅₀₄). Пусть внутри четверок матчи закончились так, как описано выше, а при $i меньше j$ команда из i-й четверки побеждает команду из j-й в основное время. Тогда из полученного распределения очков можно сделать вывод, что команда из i-й четверки действительно побеждает команду из j-й в основное время. В описанном случае внутри каждой четверки будет распределение очков 7, 7, 2, 2, поэтому будет не менее 3 овертаймов, а значит, всего овертаймов не менее 1512.

Ответ: $N=1512.$

Критерии оценивания	Балл
Полное решение	+
Неверное решение	−

Решение · Критерии · Помощь

Тип 0 № 4388 Добавить в вариант

На шахматном турнире для 12 участников каждый сыграл ровно по одной партии с каждым из остальных. За выигрыш давали 1 очко, за ничью $дробь: числитель: 1, знаменатель: 2 конец дроби ,$ за проигрыш 0. Вася проиграл только одну партию, но занял последнее место, набрав меньше всех очков. Петя занял первое место, набрав больше всех очков. На сколько очков Вася отстал от Пети?

Решение · Помощь

Тип 0 № 4400 Добавить в вариант

В шахматном турнире каждый участник встретился с каждым один раз. В каждом туре каждый участник проводил по одной встрече. Не меньше чем в половине всех встреч оба участника были земляками (из одного города). Докажите, что в каждом туре была хотя бы одна встреча между земляками.

Решение · Помощь

Тип 21 № 4427 Добавить в вариант

Несколько человек сыграли однокруговой турнир по настольному теннису. По окончании турнира оказалось, что для любых четырех участников найдутся двое, набравшие поровну очков в играх между этими четырьмя участками. Какое наибольшее количество теннисистов могло принимать участие в этом турнире? В настольном теннисе не бывает ничьих, за победу дается одно очко, за поражение  — ноль очков.

(из материалов зарубежных олимпиад)

Решение · Помощь

Тип 0 № 4677 Добавить в вариант

В футбольном турнире играли семь команд: каждая команда по одному разу сыграла с каждой. В следующий круг отбираются команды, набравшие тринадцать и более очков. За победу дается 3 очка, за ничью  — 1 очко, за поражение  — 0 очков. Какое наибольшее количество команд может выйти в следующий круг?

Критерии оценивания	Балл
Верное решение без существенных недочетов	+
В целом задача решена, хотя и с недочетами	+ −
Задача не решена, но есть заметное продвижение	− +
Задача не решена, заметных продвижений нет	−
Задача не решалась	0

Аналоги к заданию № 4677: 4678 Все

Решение · Критерии · Помощь

Тип 0 № 4678 Добавить в вариант

В футбольном турнире играли восемь команд: каждая команда по одному разу сыграла с каждой. В следующий круг отбираются команды, набравшие пятнадцать и более очков. За победу даётся 3 очка, за ничью  — 1 очко, за поражение  — 0 очков. Какое наибольшее количество команд может выйти в следующий круг?

Критерии оценивания	Балл
Верное решение без существенных недочетов	+
В целом задача решена, хотя и с недочетами	+ −
Задача не решена, но есть заметное продвижение	− +
Задача не решена, заметных продвижений нет	−
Задача не решалась	0

Аналоги к заданию № 4677: 4678 Все

Решение · Прототип задания · Критерии · Помощь

Тип 0 № 4888 Добавить в вариант

В первенстве по футболу участвует 20 команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?

Решение.

Будем рассматривать несыгранные игры. Условие означает, что несыгранные игры не образуют треугольников. Докажем индукцией по k, что для 2k команд наибольшее число несыгранных игр не больше $k в квадрате .$

База индукции: $k=1$ (оценка очевидна).

Шаг индукции: Пусть доказано для k: докажем для $k плюс 1.$ Если несыгранных игр нет, то всё доказано. Иначе выделим произвольные команды A и B, не игравшие между собой. Заметим, что несыгранных игр с участием команд A или B не более $2 k$ (не считая игры между A и B), так как для любой команды C сыграна хотя бы одна из игр AC и BC. Теперь рассмотрим все команды, кроме A и B и применим предположение индукции  — среди них не сыграно не более $k в квадрате$ игр. Отсюда общее количество несыгранных игр не более $k в квадрате плюс левая круглая скобка 2 k плюс 1 правая круглая скобка = левая круглая скобка k плюс 1 правая круглая скобка в квадрате ,$ что и требовалось доказать.

Подставляя $k=10$ получаем, что число несыгранных игр не более 100, а число всех возможных игр $дробь: числитель: 20 умножить на 19, знаменатель: 2 конец дроби =190,$ откуда число сыгранных игр не менее $190 минус 100=90.$

Оценка достигается, если разбить команды на две равные группы, в каждой из которых провести все матчи, а между группами не проводить ни одного.

Ответ: 90 игр.

Критерии проверки:

Общие критерии оценивания

По результатам проверки каждого задания выставляется одна из следующих оценок:

а) «+», «±» — задача скорее решена;

б) «∓», «−» — задача скорее не решена;

в) за задачу, к решению которой участник не приступал, ставится оценка «0».

При подведении итогов учитывается только количество в целом решенных задач - задач, за которые поставлена оценка «+» или «±».

Оценки по задачам имеются в таблице в личном кабинете участника. Оценки внутри работы и на титульном листе работы выставлены в процессе предварительной проверки и не являются основанием для апелляции.

Приведённые далее критерии описывают оценки продвижений и ошибок, встречающихся во многих работах. Поэтому они не подлежат изменению и могут быть использованы для апелляции только в случае, если вы укажете, что какое-то место в вашей работе, подходящее под один из этих критериев, оценено не в соответствии с ним.

Комментарий по оцениванию данной задачи

Приведен пример схемы турнира, при которой достигается верный ответ, но доказательство того, что меньше игр быть не могло, отсутствует или неполно — «∓».

Получен неверный ответ (за исключением арифметических ошибок) — «−».

Решение · Критерии · Помощь

Тип 0 № 4889 Добавить в вариант

В первенстве по футболу участвует 16 команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?

Решение.

Будем рассматривать несыгранные игры. Условие означает, что не найдётся трёх команд, которые вообще не играли друг с другом. Докажем индукцией по k, что для 2k команд наибольшее число несыгранных игр не больше $k в квадрате .$

База индукции: $k=1$ (оценка очевидна).

Шаг индукции: Пусть доказано для k: докажем для $k плюс 1.$ Если несыгранных игр нет, то всё доказано. Иначе выделим произвольные команды A и B, не игравшие между собой. Заметим, что несыгранных игр с участием команд A или B не более $2 k$ (не считая игры между A и B), так как для любой команды C сыграна хотя бы одна из игр AC и BC. Теперь рассмотрим все команды, кроме A и B и применим предположение индукции $минус$ среди них не сыграно не более $k в квадрате$ игр. Отсюда общее количество несыгранных игр не более $k в квадрате плюс левая круглая скобка 2 k плюс 1 правая круглая скобка = левая круглая скобка k плюс 1 правая круглая скобка в квадрате ,$ что и требовалось доказать.

Подставляя $k=8$ получаем, что число несыгранных игр не более 64, а число всех возможных игр $дробь: числитель: 16 минус 15, знаменатель: 2 конец дроби =120,$ откуда число сыгранных игр не менее $120 минус 64=56 .$

Ответ: 56 игр.

Критерии проверки:

Общие критерии оценивания

По результатам проверки каждого задания выставляется одна из следующих оценок:

а) «+», «±» — задача скорее решена;

б) «∓», «−» — задача скорее не решена;

в) за задачу, к решению которой участник не приступал, ставится оценка «0».

Комментарий по оцениванию данной задачи

Получен неверный ответ (за исключением арифметических ошибок) — «−».

Решение · Критерии · Помощь

Тип 0 № 4928 Добавить в вариант

Федерация спортивной борьбы присвоила каждому участнику соревнования квалификационный номер. Известно, что во встречах борцов, квалификационные номера которых отличаются более, чем на 2 номера, всегда побеждает борец с меньшим номером. Турнир для 256 борцов проводится по олимпийской системе: в начале каждого дня бойцы разбиваются на пары, проигравший выбывает из соревнований (ничьих не бывает). Какой наибольший квалификационный номер может иметь победитель?

Решение.

Заметим, что борец с номером k может проиграть только борцу с номером $k плюс 1$ или $k плюс 2,$ поэтому после каждого тура наименьший номер не может увеличиться больше, чем на 2 номера. На турнире с 256 участниками 8 туров, следовательно, номер победителя турнира не превосходит $1 плюс 2 умножить на 8=17.$

Предположим, что борец с номером 17 может победить. Тогда в первом туре должны выбыть борцы с номерами 1 и 2. Это возможно только если борец с номером 1 проиграл борцу с номером 3, а борец с номером 2 проиграл борцу с номером 4. Значит, после первого тура борцы с номерами 3 и 4 останутся. Аналогично, после второго тура останутся борцы с номерами 5 и 6, после третьего  — 7 и 8, ..., после седьмого  — 15 и 16. Значит, в последнем, финальном, бою встретятся борцы с номерами 15 и 16. Противоречие с предположением, что борец с номером 17 может победить.

Покажем, что борец с номером 16 может победить. Назовём борцов с номерами большими 16 слабыми. Пусть в туре с номером $k меньше или равно 7$ борец с номером $2 k минус 1$ проиграет борцу с номером $2 k плюс 1,$ борец с номером $2 k$ проиграет борцу с номером $2 k плюс 2,$ борцы с номерами $2 k плюс 3,$ ..., 16 победят каких-то слабых борцов, оставшиеся слабые борцы как-то сыграют между собой. Тогда после 7 туров останутся борцы с номерами 15 и 16, и в финальном бое борец с номером 16 победит.

Ответ: 16.

Критерии проверки:

Общие критерии оценивания

По результатам проверки каждого задания выставляется одна из следующих оценок (перечислены в порядке убывания):

а) «+» — задача решена полностью;

б) «±» — задача решена с недочетами, не влияющими на общий ход решения;

в) «∓» — задача не решена (например, в решении содержатся грубые ошибки), но имеются содержательные продвижения;

г) «−» — задача не решена;

д) за задачу, к решению которой участник не приступал, ставится оценка «0».

При подведении итогов учитывается только количество в целом решенных задач — задач, за которые поставлена оценка «+» или «±».

Комментарий по оцениванию данной задачи

Имелось в виду, что номера участников — это последовательные натуральные числа от 1 до количества участников.

Не доказано, что номер больше приведенного быть не мог (например, утверждается, но не доказано, что какой-то способ действий «очевидно является оптимальным», «логично действовать именно так» и т. п.) — не выше «∓».

Аналоги к заданию № 4928: 4930 4931 4929 Все

Решение · Критерии · Помощь

Всего: 115 1–20 | 21–40 | 41–60 | 61–80 …

	1	2	3	4	5	6	7	Сумма
1	X	0	1	3	3	3	3	13
2	3	X	0	1	3	3	3	13
3	1	3	X	0	3	3	3	13
4	0	1	3	X	3	3	3	13
5	0	0	0	0	X	1	1	2
6	0	0	0	0	1	X	1	2
7	0	0	0	0	1	1	X	2